package com.explorati.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树的非递归实现
 * 
 * @author explorati
 *
 * @param <E>
 */
public class BST1<E extends Comparable<E>> {

	public class Node<E> {
		public E e;
		public Node left, right;

		public Node(E e) {
			this.e = e;
			this.left = this.right = null;
		}
	}

	private int size;
	private Node root;

	public BST1() {
		root = null;
		size = 0;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public int getSize() {
		return size;
	}

	// 添加操作
	public void add(E e) {
		if (root == null) {
			root = new Node(e);
			size++;
			return;
		}
		Node cur = root;
		Node prev = null;
		while (cur != null) {
			if (e.compareTo((E) cur.e) == 0) {
				return;
			}
			prev = cur;
			if (e.compareTo((E) cur.e) > 0) {
				cur = cur.right;
			} else {
				cur = cur.left;
			}
		}

		cur = new Node(e);
		if (e.compareTo((E) prev.e) > 0) {
			prev.right = cur;
			size++;
		} else {
			prev.left = cur;
			size++;
		}
	}

	public boolean contains(E e) {
		Node cur = root;
		while (cur != null) {
			if (e.compareTo((E) cur.e) == 0) {
				return true;
			} else if (e.compareTo((E) cur.e) > 0) {
				cur = cur.right;
			} else {
				cur = cur.left;
			}
		}
		return false;
	}

	public List<E> preOrder() {
		List<E> res = new ArrayList<E>();

		Stack<Node> stack = new Stack<>();
		stack.push(root);

		while (!stack.isEmpty()) {
			Node cur = stack.pop();
			res.add((E) cur.e);
			if (cur.right != null) {
				stack.push(cur.right);
			}
			if (cur.left != null) {
				stack.push(cur.left);
			}
		}
		return res;
	}

	public List<E> inOrder() {
		List<E> list = new ArrayList<>();

		Stack<Node> stack = new Stack<>();

		Node cur = root;

		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			cur = stack.pop();
			list.add((E) cur.e);
			cur = cur.right;
		}

		return list;
	}
}
